Today’s Agenda

  • Motivation
  • Hausmann’s Curious Question
  • Latschev’s remarkable (but qualitative!) answer
  • Finite reconstruction problem
  • Quantitative Latschev’s theorem
    • abstract manifolds
    • Euclidean submanifolds
  • Extension to CAT(κ)\mathrm{CAT}(\kappa) Spaces
  • Questions

The Vietoris–Rips Complexes

  • a metric space (X,dX)(X,d_X)

    • a scale β>0\beta>0

    • ℛβ(X)\mathcal{R}_\beta(X) is an abstract simplicial complex such that

      • XX is the vertex set
      • each subset A⊂XA\subset X of (k+1)(k+1) points with diameter at most β\beta is a kk-simplex.

Hausmann’s Theorem

Hausmann (1995)

For any closed Riemannian manifold MM and 0<β<ρ(M)0<\beta<\rho(M), the Vietoris–Rips complex ℛβ(M)\mathcal{R}_\beta(M) is homotopy equivalent to MM.

  • vertex set is the entire manifold MM
  • Convexity Radius ρ(M)\rho(M) is the largest (sup) radius so that geodesic balls are convex.
    • ρ(S1)=π2\rho(S^1)=\frac{\pi}{2}
    • ρ(M)>0\rho(M)>0 for a compact manifold

Finite Reconstruction Problem

Hausmann’s Curious Question

What about the Vietoris–Rips complex of a dense subset X⊂MX\subset M? More generally, for a sample with a small dGH(M,X)d_{GH}(M,X).

  • The Rips alternative to Nerve Lemma
  • Manifold reconstruction from a dense subset

Hausdorff and Gromov–Hausdorff Distances

Gromov–Hausdorff Distance:

  • provides the noise model for our reconstruction problem
  • similarity measure between abstract metric spaces (X,dX)(X,d_X) and (Y,dY)(Y,d_Y)
  • Definition: dGH(X,Y)=infdHZ(f(X),g(Y))d_{GH(X,Y)}=\inf d_H^Z(f(X),g(Y))
    • inf over metric spaces (Z,dZ)(Z,d_Z) and isometries f:X→Zf:X\to Z, g:Y→Zg:Y\to Z

See (Adams et al. 2023) for more details on the relation between the Gromov–Hausdorff and Hausdorff distances.

Latschev’s Remarkable Solution

Latschev’s Theorem (Latschev 2001)

For every closed Riemannian manifold MM, there exists a positive number ϵ0\epsilon_0 such that for any 0<β≤ϵ00<\beta\leq\epsilon_0 there exists some δ>0\delta>0 such that for every metric space XX with Gromov–Hausdorff distance to MM less than δ\delta, the Vietoris–Rips complex ℛβ(X)\mathcal R_\beta(X) is homotopy equivalent to MM.

Key points:

  • The result is qualitative

  • the threshold ϵ0=ϵ0(M)\epsilon_0=\epsilon_0(M) depends solely on the geometry of MM. But the theorem did not say how!

  • δ=δ(β)\delta=\delta(\beta) is a function (probably a fraction) of β\beta.

  • Nonetheless, the result answers Hausmann’s question!

Quantitative Latschev’s Theorem

Metric Graph Reconstruction (Majhi 2023b)

Let (G,dG)(G,d_G) be a compact, path-connected metric graph, (X,dX)(X,d_X) a metric space, and β>0\beta>0 a number such that 3dGH(G,X)<β<3ρ(G)/4.3d_{GH}(G,X)<\beta<3\rho(G)/4. Then, ℛβ(X)≃G\mathcal R_\beta(X)\simeq G.

Key points:

  • The result is quantitative

  • ϵ0=3ρ(G)/4\epsilon_0=3\rho(G)/4

  • δ=β/3\delta=\beta/3

Quantitative Latschev’s Theorem

Riemannian Manifold Reconstruction (Majhi 2023a)

Let (M,dM)(M,d_M) be a closed, connected Riemannian manifold. Let (X,dX)(X,d_X) be a compact metric space and β>0\beta>0 a number such that 1ζdGH(M,X)<β<11+2ζmin{ρ(M),π4κ} \frac{1}{\zeta}d_{GH}(M,X)<\beta<\frac{1}{1+2\zeta}\min\left\{\rho(M),\frac{\pi}{4\sqrt{\kappa}}\right\} for some 0<ζ≤1/140<\zeta\leq1/14. Then, ℛβ(X)≃M\mathcal R_\beta(X)\simeq M.

Key points:

  • κ\kappa is an upper bound on the sectional curvatures of MM

  • For ζ=114\zeta=\frac{1}{14}:

    • ϵ0=78min{ρ(M),π4κ}\epsilon_0=\frac{7}{8}\min\left\{\rho(M),\frac{\pi}{4\sqrt{\kappa}}\right\}

    • δ=β14\delta=\frac{\beta}{14}

Quantitative Latschev’s Theorem

Euclidean Submanifold Reconstruction (Majhi 2023a)

Let M⊂ℝNM\subset\mathbb R^N be a closed, connected submanifold. Let X⊂ℝNX\subset\mathbb R^N be a compact subset and β>0\beta>0 a number such that 1ζdH(M,X)<β<3(1+2ζ)(1−14ζ)8(1−2ζ)2τ(M) \frac{1}{\zeta}d_{H}(M,X)<\beta<\frac{3(1+2\zeta)(1-14\zeta)}{8(1-2\zeta)^2}\tau(M) for some 0<ζ<1/140<\zeta<1/14. Then, ℛβ(X)≃M\mathcal R_\beta(X)\simeq M.

Key points:

  • τ(M)\tau(M) is the reach of MM

  • For ζ=128\zeta=\frac{1}{28}:

    • ϵ0=3151352τ(M)\epsilon_0=\frac{315}{1352}\tau(M)

    • δ=β28\delta=\frac{\beta}{28}

Beyond Manifolds

Define CAT spaces

Lastchev’s Theorem for Abstract CAT Spaces

Lastchev’s Theorem for Euclidean CAT Spaces

Discussions

References

Adams, Henry, Florian Frick, Sushovan Majhi, and Nicholas McBride. 2023. “Hausdorff Vs Gromov–Hausdorff Distances.” arXiv Preprint arXiv:2309.16648.
Chazal, Frédéric, Ruqi Huang, and Jian Sun. 2015. “Gromov–Hausdorff Approximation of Filamentary Structures Using Reeb-Type Graphs.” Discrete & Computational Geometry 53 (3): 621–49. https://doi.org/10.1007/s00454-015-9674-1.
Ge, Xiaoyin, Issam Safa, Mikhail Belkin, and Yusu Wang. 2011. “Data Skeletonization via Reeb Graphs.” In Advances in Neural Information Processing Systems, edited by J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger. Vol. 24. Curran Associates, Inc. https://proceedings.neurips.cc/paper_files/paper/2011/file/3a0772443a0739141292a5429b952fe6-Paper.pdf.
Hausmann, Jean-Claude. 1995. “On the Vietoris-Rips Complexes and a Cohomology Theory for Metric Spaces.” In Prospects in Topology (AM-138), 175–88. Princeton University Press.
Komendarczyk, Rafal, Sushovan Majhi, and Will Tran. 2024. “Topological Stability and Latschev-Type Reconstruction Theorems for CAT(𝛋)\boldsymbol{\mathrm{CAT}(κ)} Spaces.”
Latschev, J. 2001. “Vietoris-Rips Complexes of Metric Spaces Near a Closed Riemannian Manifold.” Archiv Der Mathematik 77 (6): 522–28. https://doi.org/10.1007/PL00000526.
Majhi, Sushovan. 2023a. “Demystifying Latschev’s Theorem: Manifold Reconstruction from Noisy Data.”
arXiv:2204.14234 [Math.AT]. https://doi.org/10.48550/ARXIV.2305.17288.
———. 2023b. “VietorisRips Complexes of Metric Spaces Near a Metric Graph.” Journal of Applied and Computational Topology, May. https://doi.org/10.1007/s41468-023-00122-z.